package com.leetcode.algorithm.y18.m05;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * leetcode-cn.com
 * 1.两数之和
 * 7.反转整数
 * 9.回文数
 * 13.罗马数字转整数
 * 14. 最长公共前缀
 * @author: jie.deng
 * @time: 2018年5月31日 下午1:04:24
 */
public class MySolution0504 {
	
	/**
	 * 1.两数之和 
	 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 
	 * 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 
	 * 示例:
	 * 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9
	 * 所以返回 [0, 1]
	 * @param nums
	 * @param target
	 * @return
	 * @author: jie.deng
	 * @time: 2018年5月4日 下午1:29:58
	 */
	public int[] twoSum(int[] nums, int target) {
		for (int i = 0; i < nums.length; i++) {
			int i1 = nums[i];
			for (int j = i + 1; j < nums.length; j++) {
				if (i1 + nums[j] == target) {
					return new int[] { i, j };
				}
			}
		}
		return nums;
	}
	
	/**
	 * 7.反转整数 
	 * 给定一个 32 位有符号整数，将整数中的数字进行反转。
	 * 
	 * 示例 1:
	 * 输入: 123 输出: 321 
	 * 示例 2:
	 * 输入: -123 输出: -321 
	 * 示例 3:
	 * 输入: 120 输出: 21 
	 * 
	 * 注意:
	 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
	 * 
	 * @param x
	 * @return
	 * @author: jie.deng
	 * @time: 2018年5月4日 下午5:19:46
	 */
    public int reverse(int x) {
		if (x == Integer.MIN_VALUE) {
			return 0;
		}
		boolean negativeFlag = (x < 0);
		if (negativeFlag) {
			x = -x;
		}
		String revStr = new StringBuffer("" + x).reverse().toString();
		if (revStr.length() == 10 && revStr.compareTo("" + (Integer.MAX_VALUE - (negativeFlag ? 1 : 0))) > 0) {
			return 0;
		} else {
			int parseInt = Integer.parseInt(revStr);
			return negativeFlag ? -parseInt : parseInt;
		}
    }
    
	/**
	 * 9.回文数 
	 * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 
	 * 示例 1:
	 * 输入: 121 输出: true 
	 * 示例 2:
	 * 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 
	 * 示例 3:
	 * 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。 
	 * 
	 * 进阶:
	 * 你能不将整数转为字符串来解决这个问题吗？
	 * @param x
	 * @return
	 * @author: jie.deng
	 * @time: 2018年5月4日 下午5:06:55
	 */
	public boolean isPalindrome(int x) {
		if (x < 0) {
			return false;// 负数不是回文数
		}
		if (x < 10) {
			return true;// 10以内的整数是回文数
		}
		int len = ("" + x).length();
		int div = 1;
		for (int i = 1; i < len; i++) {
			div *= 10;
		}
		int i = 1;
		while (x % 10 == x / div) {
			x -= x / div * div;
			x /= 10;
			div /= 100;
			i += 1;
			if (i > len / 2) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 13.罗马数字转整数
	 * 
	 * 罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。
	 * 
	 * 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12
	 * 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
	 * 
	 * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5
	 * 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
	 * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 
	 * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
	 * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 
	 * 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
	 * 
	 * 示例 1:
	 * 输入: "III" 输出: 3 
	 * 示例 2:
	 * 输入: "IV" 输出: 4 
	 * 示例 3:
	 * 输入: "IX" 输出: 9 
	 * 示例 4:
	 * 输入: "LVIII" 输出: 58 解释: C = 100, L = 50, XXX = 30, III = 3. 
	 * 示例 5:
	 * 输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
	 * 
	 * @param s
	 * @return
	 */
	public int romanToInt(String s) {
		int sum = 0;
		int len = s.length();
		int i = 0;
		while (s.startsWith("M", i)) {
			sum += 1000;
			i++;
		}
		if (s.startsWith("CM", i)) {
			sum += 900;
			i += 2;
		} else if (s.startsWith("CD", i)) {
			sum += 400;
			i += 2;
		} else {
			if (s.startsWith("D", i)) {
				sum += 500;
				i++;
			}
			while (s.startsWith("C", i)) {
				sum += 100;
				i++;
			}
		}
		if (s.startsWith("XC", i)) {
			sum += 90;
			i += 2;
		} else if (s.startsWith("XL", i)) {
			sum += 40;
			i += 2;
		} else {
			if (s.startsWith("L", i)) {
				sum += 50;
				i++;
			}
			while (s.startsWith("X", i)) {
				sum += 10;
				i++;
			}
		}
		if (s.startsWith("IX", i)) {
			sum += 9;
			i += 2;
		} else if (s.startsWith("IV", i)) {
			sum += 4;
			i += 2;
		} else {
			if (s.startsWith("V", i)) {
				sum += 5;
				i++;
			}
			while (s.startsWith("I", i)) {
				sum += 1;
				i++;
			}
		}
		return i==len?sum:0;
	}
    public int romanToIntPattern(String s) {
    	Pattern pattern = Pattern.compile("(M{1,3})?((CM)|(CD)|((D)?(C{1,3})))?((XC)|(XL)|((L)?(X{1,3})))?((IX)|(IV)|((V)?(I{1,3})))?");
    	Matcher matcher = pattern.matcher(s);
    	System.out.println(matcher.matches());
    	int sum = 0;
    	if (matcher.matches()) {
    		sum += matcher.group(1)==null?0:(matcher.group(1)).length()*1000;
    		if (matcher.group(2) != null) {
    			if (matcher.group(3) != null) {
    				sum += 900;
    			}else if (matcher.group(4) != null) {
    				sum += 400;
    			}else if (matcher.group(5) != null) {
    				if (matcher.group(6) != null) {
    					sum += 500;
    				}
    				if (matcher.group(7) != null) {
    					sum += (matcher.group(7)).length()*100;
    				}
    			}
    		}
    		if (matcher.group(8) != null) {
    			if (matcher.group(9) != null) {
    				sum += 90;
    			}else if (matcher.group(10) != null) {
    				sum += 40;
    			}else if (matcher.group(11) != null) {
    				if (matcher.group(12) != null) {
    					sum += 50;
    				}
    				if (matcher.group(13) != null) {
    					sum += (matcher.group(13)).length()*10;
    				}
    			}
    		}
    		if (matcher.group(14) != null) {
    			if (matcher.group(15) != null) {
    				sum += 9;
    			}else if (matcher.group(16) != null) {
    				sum += 4;
    			}else if (matcher.group(17) != null) {
    				if (matcher.group(18) != null) {
    					sum += 5;
    				}
    				if (matcher.group(19) != null) {
    					sum += (matcher.group(19)).length();
    				}
    			}
    		}
    	}
    	return sum;
    }
   
	/**
	 * 14. 最长公共前缀
	 * 编写一个函数来查找字符串数组中的最长公共前缀。
	 * 如果不存在公共前缀，返回空字符串 ""。
	 * 
	 * 示例 1:
	 * 输入: ["flower","flow","flight"] 输出: "fl" 
	 * 示例 2:
	 * 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 
	 * 说明:
	 * 所有输入只包含小写字母 a-z 。
	 * 
	 * @param strs
	 * @return
	 */
    public String longestCommonPrefix(String[] strs) {
    	if (strs == null) {
    		return "";
		}
    	
    	int len = strs.length;
		if (len == 0) {
			return "";
		}
		String commonPrefix = strs[0];
        for (int i = 1; i < len && !"".equals(commonPrefix); i++) {
        	while (!strs[i].startsWith(commonPrefix)) {
        		commonPrefix = commonPrefix.substring(0, commonPrefix.length()-1);
			}
		}
    	return commonPrefix;
    }
    
}